1. Field of the Invention
The present invention relates to a network switching device and a network switching method for transferring variable-length packets between a plurality of networks. More particularly, the present invention relates to a network switching device and a network switching method using a shared buffer as temporary packet storage.
2. Description of the Related Art
Network switching devices are often used to interconnect many network segments, as in the Internet and other large-scale networks. The most widely used are those with an internal buffer to temporarily store received packets and inspect their integrity of the received packets before directing them to intended destination ports. This type of switching mechanism is called “store and forward” switching. In many of today's communications network systems, data is transmitted in the form of variable-length packets. According to, for example, the Internet Protocol (IP), a variable-length packet called “IP datagram” carries each message over the network.
FIG. 15 shows an example of a conventional network switching device. The illustrated network switching device transfers packets to and from a plurality of networks 201 to 204. To this end, the device has a plurality of receive interfaces 211 to 214 and their corresponding receive buffers 221 to 224 for reception from different networks 201 to 204, a plurality of transmit interfaces 231 to 234 and their corresponding transmit buffers 241 to 244 for transmission to different networks 201 to 204, and a data transfer circuit 250. To aid the understanding, FIG. 15 shows the receive interfaces 211 to 214 as separate elements from transmit interfaces 231 to 234, although those two sets of interfaces may actually be unified.
The receive interfaces 211 to 214 are connected to different networks 201 to 204, respectively, as are the transmit interfaces 231 to 234. Packets that those receive interfaces 211 to 214 have received from their attached networks 201 to 204 are temporarily stored in the corresponding receive buffers 221 to 224. The data transfer circuit 250 retrieves packets stored in the receive buffers 221 to 224 and routes each packet to an appropriate transmit buffer corresponding to the destination port of that packet. Then the packets stored in each transmit buffer 241 to 244 are read out in response to a transmission request from the corresponding transmit interface 231 to 234 for transmission to the intended networks 201 to 204.
A drawback of the network switching device shown in FIG. 15 is that the device demands a large memory capacity since it has to reserve a number of buffer areas in its memory space to provide a dedicated buffer for each receive port and transmit port. Another known network switching device addresses this problem in memory capacity by providing a single shared buffer to accommodate all incoming and outgoing packets. The following will discuss the network switching device of this type.
FIG. 16 shows an example of a conventional network switching device with a shared buffer. Similar to that of FIG. 15, the network switching device of FIG. 16 transfers packets between a plurality of networks 301 to 304. To this end, the network switching device has the following elements: receive interfaces 311 to 314 corresponding to different networks 301 to 304, transmit interfaces 321 to 324 corresponding to different networks 301 to 304, a receive data transfer circuit 330 for handling incoming packets, a transmit data transfer circuit 340 for handling outgoing packets, and a shared buffer 350 for storing the both. To aid the understanding, FIG. 16 shows two data transfer circuits 330 and 340 as separate elements, although the receiving circuit and sending circuit can be unified in the actual implementation. This applies also to the receive interfaces 311 to 314 and transmit interfaces 321 to 324.
The receive interfaces 311 to 314 receive packets from their corresponding networks 301 to 304. The receive data transfer circuit 330 save them in the shared buffer 350 successively. Upon receipt of a transmission request from each transmit interface 321 to 324, the transmit data transfer circuit 340 delivers packets from the shared buffer 350 to an appropriate transmit interface corresponding to the destination of each packet. The transmit interfaces 321 to 324 output those packets from the shared buffer 350 to their attached networks 301 to 304.
The network switching devices described in FIGS. 15 and 16 are usually designed to manage outbound packets for each particular destination port by using a queue with a linked list structure in which the pending packets are linked one after another. To store variable-length packets, many such buffers are configured to handle data in units of the maximum packet length and to manage individual packets by using pointers. One advantage of this architecture is its ease of control. For example, a packet received with errors can be discarded easily by simply deleting a pointer to that packet. Nevertheless, the buffer consumes large amounts of memory space, which equals the maximum packet length multiplied by the maximum number of packets to be stored. Suppose now that most received packets are far smaller than the assumed maximum packet length. In this case, a large portion of the buffer remains unused, meaning that the memory efficiency decreases.
There has therefore been a demand for a packet switch with an improved common buffer memory architecture that can handle variable-length packets more efficiently. In one example of such a packet switch, variable-length packets received from each input channel are written into a common buffer memory in the form of fixed-length data blocks. A buffer controller is employed to create an input queue for each input channel during the process of writing data blocks. After the last data block is registered with the input queue, the linked address list of that input queue is linked to an output queue corresponding to the specified destination channel.
Input queues are created in the process of writing packets into the common buffer memory, by placing, in a next address memory, a record of the write address of each next fixed-length data block. Output queues, on the other hand, are formed as address tables containing “next read address” indicating which data block to read next, together with “last read address” indicating where the last data block is. The buffer controller has an input queue controller which establishes a linkage from an input queue to an output queue by transporting the addresses of top and last data blocks of each variable-length packet, respectively, to the next and last read addresses in an address table corresponding to the destination channel. If the address table has a registered last read address for a preceding variable-length packet, the input queue controller makes access to the next address memory to extract therefrom the write address of the top data block of a succeeding variable-length packet. The input queue controller then creates a linkage from the extracted address to the existing last read address. By controlling the common buffer memory in this way, the above-described packet switch increases switching speeds, besides improving the efficiency of memory usage. See, for example, paragraphs 0025 to 0040 and FIG. 3 of Japanese Unexamined Patent Publication No. 2002-152247.
There is another example of a packet switch with a common buffer memory storing variable-length packets as a collection of fixed-length data blocks. Similarly to the foregoing example, the buffer controller in this packet switch creates an input queue for each individual input channel to store data in the buffer memory. After the last data block is registered with the input queue, the linked address list of that input queue is linked to an output queue corresponding to the specified destination channel. Unlike the foregoing, this packet switch has a waiting buffer and an address memory that serve as an output queue. The waiting buffer temporarily stores write addresses of top and last data blocks of each variable-length packet. The address memory stores next read addresses indicating which data block to read next, together with last read addresses indicating where the last data block is. The buffer controller has an input queue controller and an output queue controller. The input queue controller registers the write addresses of top and last data blocks of each received variable-length packet with a waiting buffer corresponding to the specified destination channel. When the accompanying address memory is emptied, the output queue controller retrieves a pair of addresses from the waiting buffer and sends them to the address memory as the next and last read addresses of a new set of data blocks. In this way, the packet switch increases switching speeds, besides improving the efficiency of buffer memory usage. See, for example, paragraphs 0025 to 0037 and FIG. 3 of Japanese Unexamined Patent Publication No. 2002-185495.
The network switching device with a shared buffer explained in FIG. 16 may experience a concentrated traffic of incoming packets destined to a particular port. Due to the resulting congestion, the shared buffer could be occupied by outgoing packets addressed to the same port. In this situation, some other ports could suffer a decrease of throughput as a result of congestion inside the shared buffer, although the ports are supposed to work independently of each other. This problem is generally known as “blocking.”
The network switching device of FIG. 15 is free from the blocking problem described above, because of its independent receive and transmit buffers disposed for each port. However, as mentioned earlier, the problem with this configuration is that a large buffer capacity is required, and it leads to an increased component cost.
The packet switches disclosed in the aforementioned Japanese Unexamined Patent Publication Nos. 2002-152247 and 2002-185495 make it possible to improve the use efficiency of their common buffer memory in storing received variable-length packets. Those devices, however, lack the ability to avoid a blocking problem.